import sys
from collections import deque


class Edge:
    def __init__(self, to, cost, capacity, rev):
        self.to = to
        self.cost = cost
        self.capacity = capacity
        self.rev = rev


class MinCostFlowSolver:
    def __init__(self, n, edges):
        self.n = n
        self.edges = edges
        self.paths = [[], []]
        self.total_cost = 0

    def solve(self):
        max_nodes = self.n + 3
        e = [[] for _ in range(max_nodes)]

        def add_edge(u, v, cost, cap):
            e[u].append(Edge(v, cost, cap, len(e[v])))
            e[v].append(Edge(u, -cost, 0, len(e[u]) - 1))

        for u, v, w in self.edges:
            add_edge(u, v, w, 1)
            add_edge(v, u, w, 1)

        s = self.n + 1
        t = self.n + 2
        add_edge(s, 1, 0, 2)
        add_edge(self.n, t, 0, 2)

        INF = float('inf')
        path_count = 0

        while path_count < 2:
            dist = [INF] * (self.n + 3)
            dist[s] = 0
            in_queue = [False] * (self.n + 3)
            q = deque([s])
            pre = [-1] * (self.n + 3)
            pre_edge = [0] * (self.n + 3)

            while q:
                u = q.popleft()
                in_queue[u] = False
                for i, edge in enumerate(e[u]):
                    if edge.capacity > 0 and dist[edge.to] > dist[u] + edge.cost:
                        dist[edge.to] = dist[u] + edge.cost
                        pre[edge.to] = u
                        pre_edge[edge.to] = i
                        if not in_queue[edge.to]:
                            in_queue[edge.to] = True
                            q.append(edge.to)

            if dist[t] == INF:
                break

            flow = INF
            v = t
            path = []
            while pre[v] != -1:
                u = pre[v]
                edge_index = pre_edge[v]
                flow = min(flow, e[u][edge_index].capacity)
                if 1 <= v <= self.n:
                    path.append(v)
                v = u
            path.append(1)
            path.reverse()

            unique_path = []
            last = -1
            for node in path:
                if node != last:
                    unique_path.append(node)
                    last = node

            if path_count == 0:
                self.paths[0] = unique_path
            else:
                self.paths[1] = unique_path[::-1]

            path_count += 1

            v = t
            while pre[v] != -1:
                u = pre[v]
                edge_index = pre_edge[v]
                e[u][edge_index].capacity -= flow
                e[v][e[u][edge_index].rev].capacity += flow
                v = u

            self.total_cost += dist[t] * flow

        return self.paths[0], self.paths[1], self.total_cost


def load_test_cases(file_path):
    test_cases = []
    with open(file_path, 'r') as f:
        while True:
            # 读取节点和边数
            line = f.readline()
            if not line:  # 文件结束
                break
            line = line.strip()
            if not line:  # 跳过空行
                continue

            try:
                n, m = map(int, line.split())
            except ValueError:
                print(f"警告: 跳过格式错误的行: {line}")
                continue

            edges = []
            edges_read = 0
            # 读取m条边
            while edges_read < m:
                edge_line = f.readline()
                if not edge_line:
                    break  # 文件意外结束
                edge_line = edge_line.strip()
                if not edge_line:  # 跳过空行
                    continue

                try:
                    u, v, w = map(int, edge_line.split())
                    edges.append((u, v, w))
                    edges_read += 1
                except ValueError:
                    print(f"警告: 跳过格式错误的边: {edge_line}")
                    continue

            # 检查是否读取了足够的边
            if len(edges) != m:
                print(f"警告: 测试用例期望 {m} 条边，但只找到 {len(edges)} 条")

            if edges:  # 只有包含边的测试用例才添加
                test_cases.append((n, m, edges))

            # 跳过测试用例后的空行
            while True:
                pos = f.tell()  # 记录当前位置
                line = f.readline()
                if not line or line.strip():
                    f.seek(pos)  # 如果不是空行，回退
                    break

    print(f"从文件加载了 {len(test_cases)} 个测试用例")
    return test_cases


def run_tests(test_cases):
    if not test_cases:
        print("错误: 没有加载任何测试用例")
        return

    print(f"\n{'=' * 50}")
    print(f"开始执行 {len(test_cases)} 个测试用例")
    print(f"{'=' * 50}\n")

    for idx, (n, m, edges) in enumerate(test_cases, 1):
        print(f"{'-' * 30}")
        print(f"测试用例 {idx}:")
        print(f"节点数: {n}, 边数: {m}")
        print("边列表:")
        for u, v, w in edges:
            print(f"  {u} -> {v} (权重: {w})")

        solver = MinCostFlowSolver(n, edges)
        path1, path2, total_cost = solver.solve()

        if not path1 or not path2:
            print("\n结果: 无法找到有效的往返路径\n")
            continue

        print(f"\n结果: 最短路径总长度: {total_cost}")
        print(f"去程路径 (1 -> {n}): {' -> '.join(map(str, path1))}")
        print(f"回程路径 ({n} -> 1): {' -> '.join(map(str, path2))}")
        print(f"{'-' * 30}\n")


if __name__ == "__main__":
    if len(sys.argv) < 2:
        print("用法: 终端输入 -> python 自动化测试.py 测试数据.txt")
        sys.exit(1)

    test_cases = load_test_cases(sys.argv[1])
    run_tests(test_cases)